/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：零钱兑换</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/coin-change/
 * </pre>
 * <p>创建日期：2019年11月28日下午4:47:00</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code322CoinChange</p>
 * 查看帮助：<a href="" target="_blank"></a>
 *
 * 作者：yinjun 
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code322CoinChange
{
	public static void main(String[] args)
	{
		/**
		 * 给定不同面额的硬币 coins 和一个总金额
		 * amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
		 * 
		 * 示例 1:
		 * 
		 * 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
		 * 
		 * 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。
		 * 
		 * 
		 */
		int[] coins = new int[] { 1, 2, 5 };
		int coinChange = coinChange(coins, 11);
		System.out.println(coinChange);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		记硬币集合为：coins
	 * 		记dp[i]表示组成金额i的最少硬币数量
	 * 		则有：
	 * 			dp[i] = min({dp[i-coins[j]]...}+1),
	 * 					{dp[i-coins[j]]}：表示当前金额减去各种不同面额所剩下的钱，可以通过硬币组成的最少数量
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n)
	 * 
	 * @param coins
	 * @param amount
	 * @return
	 */
	public static int coinChange(int[] coins, int amount)
	{
		//1.硬币集合不存在则直接返回-1
		if (coins == null || coins.length <= 0)
		{
			return -1;
		}
		/**
		 * dp[amount]=min(dp[amount-coins[i]]+1)
		 */
		//2.初始化dp数组，长度为金额+1,因为还有金额0的情况
		int[] dp = new int[amount + 1];
		//3.初始化金额为0的情况
		dp[0] = 0;
		//4.外层循环控制金额的大小
		for (int i = 1; i < dp.length; i++)
		{
			//5.内层循环控制硬币数额的轮训比较
			for (int j = 0; j < coins.length; j++)
			{
				//6.由于我们需要每次比较各种组合的最小值，避免初始化值0的影响，因此在比较开始之前，将dp[i]初始化为金额+1
				dp[i] = j == 0 ? amount + 1 : dp[i];
				//7.如果硬币的面额不超过金额，则进行组合比较，不然就跳过
				if (coins[j] <= i)
				{
					//8.比较每种硬币的组合数量，取最小值
					/**
					 * 这里的意思是
					 * 假如有硬币 1 2 5   金额为：11
					 * 则
					 * 		情况1：假如组合里面有硬币1一枚，则金额剩下10，则金额10的组合数量+1就是11的一种组合数量，记为S1
					 * 		情况2：假如组合里面有硬币2一枚，则金额剩下9，则金额9的组合数量+1就是11的一种组合数量，记为S2
					 * 		情况3：假如组合里面有硬币5一枚，则金额剩下6，则金额6的组合数量+1就是11的一种组合数量，记为S3
					 * 		上面三种情况则是内层循环走完的情况，我们取其中最小的min(S1,S2,S3)即可
					 * 		上面说的情况是外层循环走最后一次的情况，也就是解题的答案的情况
					 * 		而前面的金额-1次循环是在求上面列举的三种情况里剩余金额的硬币最少组合数量
					 * 
					 * 	基本算是倒着推公式，正着解答案
					 */
					dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
				}
			}
		}
		for (int i = 0; i < dp.length; i++)
		{
			System.out.print(dp[i] + "\t");
		}
		System.out.println();
		//因为我们给每个dp[i]初始的amount+1,所以dp[amount]>amount,即没有可组合的情况
		return dp[amount] > amount ? -1 : dp[amount];
	}
}
